/*
Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	void coreSubsetsWithDup(vector<int>& nums, int level, vector<int> &item, vector<vector<int> > &result)
	{
		if (level == nums.size())
		{
			if (find(result.begin(), result.end(), item) != result.end() )
			{
				
				return;

			}
			result.push_back(item);
			
			
			return;

		}

		coreSubsetsWithDup(nums, level + 1, item, result);

		item.push_back(nums[level]);

		coreSubsetsWithDup(nums, level + 1, item, result);

		item.pop_back();

	}


	vector<vector<int>> subsetsWithDup(vector<int>& nums) {

		vector<vector<int> > result;
		vector<int> temp;


		sort(nums.begin(), nums.end());
		
		coreSubsetsWithDup(nums, 0, temp, result);

		return result;

	}
};

int main()
{
	cout << "Subsets :  " << endl;

	int length;
	cout << "Input the length: " << endl;

	cin >> length;

	vector<int> nums;
	while (length--)
	{
		int item;
		cin >> item;
		nums.push_back(item);
	}


	Solution s;
	vector<vector<int> > result;

	result = s.subsetsWithDup(nums);

	cout << "The result: " << endl;

	system("pause");

	return 0;
}